package leetcode.top100;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author ：zsy
 * @date ：Created 2022/11/10 10:00 PM
 * @description：
 */
public class _031_下一个排列 {
    @Test
    public void test() {
        // int[] nums = {1,2,3,4,8,7,6,5};
        // int[] nums = {4, 6, 5};
        int[] nums = {5, 6, 4};
        // int[] nums = {2,3,1};
        new Solution().nextPermutation(nums);
        System.out.println(Arrays.toString(nums));
    }

    class Solution {

        public void nextPermutation(int[] nums) {
            int len = nums.length;
            int i = len - 2;
            // 从后面开始找第一个顺序的点
            while (i >= 0 && nums[i] >= nums[i + 1]) i--;
            if (i >= 0) {
                int j = len - 1;
                while (j >= 0 && nums[i] >= nums[j]) j--;
                swap(nums, i, j);
            }
            reverse(nums, i + 1);
        }

        private void reverse(int[] nums, int start) {
            for (int i = start; i < start + (nums.length - start) / 2; i++) {
                swap(nums, i, nums.length - i - 1 + start);
            }
        }

        private void swap(int[] nums, int i, int j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }
}
